import heapq


class GridMaster(object):
    def canMove(self, direction: str) -> bool:
        pass

    def move(self, direction: str) -> int:
        pass

    def isTarget(self) -> None:
        pass


class Solution(object):
    # 方向列表
    _DIRECTIONS = [(0, 1, "U"), (0, -1, "D"), (1, 0, "L"), (-1, 0, "R")]

    # 方向的反方向列表
    _OPPOSITE = {"U": "D", "D": "U", "L": "R", "R": "L"}

    def __init__(self):
        # 构造地图：从(100,100)出发，地图大小在[1,100]，所以需要201来避免越界
        self.grid = [[0 for _ in range(201)] for _ in range(201)]

        self.visited = set()

        # 目标位置坐标
        self.target = (-1, -1)

        # 机器人变量
        self.master = None

    def findShortestPath(self, master: 'GridMaster') -> int:
        self.master = master

        # ---------- 深度优先搜索构造地图及成本 ----------
        # 从(100,100)出发，地图大小在[1,100]，所以需要201来避免越界
        self.dfs(100, 100)

        # 在地图中没有找到目标位置
        if self.target == (-1, -1):
            return -1

        # ---------- Dijkstra算法计算最小成本路径 ----------
        # 构造维护当前最近距离的堆
        heap = [(0, 100, 100)]

        self.visited = {(100, 100)}

        while heap:
            cost, x1, y1 = heapq.heappop(heap)

            # 如果已经到达目标位置
            if (x1, y1) == self.target:
                return cost

            for dx, dy, d in self._DIRECTIONS:
                x2, y2 = x1 + dx, y1 + dy
                if 0 <= x2 <= 200 and 0 <= y2 <= 200 and (x2, y2) not in self.visited and self.grid[x2][y2]:
                    heapq.heappush(heap, (cost + self.grid[x2][y2], x2, y2))
                    self.visited.add((x2, y2))

        return -1

    def dfs(self, x, y):
        self.visited.add((x, y))

        # 判断当前位置是否为目标位置
        if self.master.isTarget():
            self.target = (x, y)

        for dx, dy, d in self._DIRECTIONS:
            if (x + dx, y + dy) not in self.visited and self.master.canMove(d):
                self.grid[x + dx][y + dy] = self.master.move(d)  # 记录当前位置的移动成本
                self.dfs(x + dx, y + dy)
                self.master.move(self._OPPOSITE[d])  # 向相反方向移动返回之前的位置


if __name__ == "__main__":
    pass
